Typically, in an information processing apparatus employing a virtual storage system, a conversion table (page table) for conversion of virtual addresses into physical addresses is placed in a main memory unit. Then, while executing a program that has been loaded in the main memory unit, a CPU converts virtual addresses into physical addresses and uses the converted physical addresses for referring to instructions and data in the program that has been loaded in the main memory unit.
At present, the operating speed of a main memory unit is slower as compared to the operating speed of a CPU. Moreover, a CPU and a main memory unit are spaced apart by a large distance. Thus, an access to a main memory unit from a CPU consumes a substantial processing time. Furthermore, since the conversion table for conversion of virtual addresses to physical addresses is placed in a main memory unit, it takes time if the conversion table is referred every time an instruction or data is to be retrieved from a program.
Given that factor, an information processing apparatus is in use in which a cache memory that is referred to as a TLB (Translation Look-aside Buffer) and controlled by an LRU (Least Recently Used) is used to register a portion of a conversion table that has been placed in a main memory unit. Then, to convert a virtual address into a physical address, a CPU in that information processing apparatus first refers to the TLB and, only when the intended entry is not found in the TLB, refers to the conversion table stored in the main memory unit. In recent years, an information processing apparatus is being used in which a full associative TLB and a 2-way set associative TLB are placed on the same hierarchy (e.g., see Japanese Laid-open Patent Publication No. 2005-346358).
Given below is the description of an information processing apparatus in which a full associative TLB and a 2-way set associative TLB are placed on the same hierarchy. FIG. 10 is a schematic diagram of a conventional information processing apparatus in which a full associative TLB and a 2-way set associative TLB are placed on the same hierarchy. Consider an architecture, as illustrated in FIG. 10, in which a full associative TLB and a 2-way set associative TLB are placed on the same hierarchy and that can process a plurality of page sizes. In that architecture, no entry is registered at the start in any of the two TLBs. Then, for the first time of TLB registration, an entry is registered in a way 0 of the sTLB as well as the fTLB according to an LRU. Regarding TLB registration according to the present invention, it is assumed that all entries are registered in a set associative TLB.
When a program is executed in such a configuration, a CPU refers to both the full associative TLB and the 2-way set associative TLB to perform conversion of a virtual address into a physical address (entry A). If a conversion table for conversion of virtual addresses is not registered in either of the two TLBs, then the CPU accesses a main memory unit for referring to a conversion table placed therein, reads the conversion table (entry A) corresponding to the target virtual address for conversion from the main memory unit, and registers it in the 2-way set associative TLB (see (1) in FIG. 10).
Subsequently, if a TLB miss occurs when the CPU refers to the TLBs for a virtual address in the same cache line of the set associative TLB, then the CPU performs an operation identical to (1) in FIG. 10 and registers the intended entry as an entry B in a way 1 of the set associative TLB (see (2) in FIG. 10). Moreover, if a TLB miss occurs when the CPU subsequently refers to the TLBs for a virtual address in the same cache line of the set associative TLB, then the CPU performs an operation identical to (1) in FIG. 10 and registers the intended entry as an entry C in the way 0 of the set associative TLB according to an LRU. However, in that case, the entry A that has already been registered is evicted from the set associative TLB (see (3) in FIG. 10).
Furthermore, if a TLB miss occurs when the CPU subsequently refers to the TLBs for a virtual address in the same cache line of the set associative TLB, then the CPU performs an operation identical to (1) in FIG. 10 and registers the intended entry as an entry D in the way 1 of the set associative TLB according to an LRU. However, in that case, the entry B that has already been registered is evicted from the set associative TLB (see (4) in FIG. 10).
However, in the abovementioned conventional technology, thrashing occurs thereby causing degradation in the processing performance. More particularly, a set associative TLB generally employs a set associative system of a number of ways. For example, consider a case when a plurality of processes is concurrently executed and the virtual addresses that compete for a cache line accessing a cache locally exceed the number of ways of a set associative TLB. In that case, TLB rewriting or, in other words, thrashing occurs. That forces the CPU to access the conversion table placed in the main memory unit. As a result, there is degradation in the processing performance.